package leetcode.code0297;

import java.util.LinkedList;
import java.util.Queue;

import leetcode.helper.tree.TreeNode;

/**
 * 执行用时：14 ms, 在所有 Java 提交中击败了69.45%的用户
 *
 * 内存消耗：40.4 MB, 在所有 Java 提交中击败了70.90%的用户
 *
 * 通过测试用例：52 / 52
 */
public class Codec1Queue {
	// Encodes a tree to a single string.
	public String serialize(TreeNode root) {
		if (root == null) {
			return "";
		}
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		int levelSize = 1;
		StringBuffer ans = new StringBuffer();
		int emptySize = 0;
		while (!queue.isEmpty()) {
			levelSize = queue.size();
			if (emptySize == levelSize) {// 这一层全是空，不玩了
				break;
			}
			emptySize = 0;// 记录下一层null的数量
			while (levelSize > 0) {
				TreeNode tn = queue.poll();
				if (tn != null) {
					ans.append(tn.val).append(",");
					queue.add(tn.left);
					queue.add(tn.right);
					if (tn.left == null) {
						emptySize++;// 添加了一个null到下一层
					}
					if (tn.right == null) {
						emptySize++;
					}
				} else {
					ans.append("null").append(",");// null占位
				}
				levelSize--;
			}
		}
		return ans.deleteCharAt(ans.length() - 1).toString();
	}

	// Decodes your encoded data to tree.
	public TreeNode deserialize(String data) {
		if (data == null || data.equals("")) {
			return null;
		}
		String[] datas = data.split(",");
		int len = datas.length;
		TreeNode ans = new TreeNode(Integer.valueOf(datas[0]));
		int levelSize = 1;// 队里新添加了几个点
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(ans);
		int p = 1;// index==0作为第一个点默认加入队列了。所以数组从index==1的位置开始。
		TreeNode tn = null;
		while (p < len) {
			int curLevel = levelSize << 1;// 这一层要处理的数量是新增点数量的2倍。
			levelSize = 0;// 新增点归零。
			while (curLevel > 0) {
				if ((p & 1) == 1) {// 奇数点取上一层的父节点
					tn = queue.poll();
					if (!datas[p].equals("null")) {
						tn.left = new TreeNode(Integer.valueOf(datas[p]));// 奇数点添加左树
						queue.add(tn.left);
						levelSize += 1;
					}
				} else {
					if (!datas[p].equals("null")) {
						tn.right = new TreeNode(Integer.valueOf(datas[p]));// 偶数点添加右树
						queue.add(tn.right);
						levelSize += 1;
					}
				}
				curLevel--;// 这一层处理的数据量-1
				p++;// 被处理数组向后移动1
			}
		}
		return ans;
	}

	public static void main(String[] args) {
		Codec1Queue codec = new Codec1Queue();
		TreeNode root = new TreeNode(1);
		root.left = new TreeNode(2);
		root.right = new TreeNode(3);
		root.right.left = new TreeNode(4);
		root.right.right = new TreeNode(5);
		root.right.left.left = new TreeNode(6);
		root.right.left.left.right = new TreeNode(7);
		String ans = codec.serialize(root);
		System.out.println(ans);
		TreeNode tn = codec.deserialize(ans);
		System.out.println(codec.serialize(tn));
	}
}
